import java.util.List;

class ListNode{
    int val;
    ListNode next;

    public ListNode(int val) {
        this.val = val;
    }
}
public class MyListNode {
    public ListNode head;
    public void create(){
        ListNode listNode1 = new ListNode(1);
        ListNode listNode2 = new ListNode(15);
        ListNode listNode3 = new ListNode(19);
        ListNode listNode4 = new ListNode(21);
        ListNode listNode5 = new ListNode(16);
        listNode1.next = listNode2;
        listNode2.next = listNode3;
        listNode3.next = listNode4;
        listNode4.next = listNode5;
        head = listNode1;
    }

    public void disply(){
        ListNode cur = head;
        while (cur != null){
            System.out.print(cur.val + " ");
            cur = cur.next;
        }
        System.out.println();

    }

    public void disply1(ListNode Newhead){
        ListNode cur = Newhead;
        while (cur != null){
            System.out.print(cur.val + " ");
            cur = cur.next;
        }
        System.out.println();

    }

    public void clear(){
        if (head == null){
            return;
        }
        while (head != null){
            ListNode cur = head.next;
            head.next = null;
            head = cur;
        }
    }

    public int size(){
        ListNode cur = head;
        int count = 0;
        while (cur != null){
            count++;
            cur = cur.next;
        }
        return count;
    }

    public void addFirst(int data){
        ListNode node = new ListNode(data);
        if (head == null){
            head = node;
        }else {
            node.next = head;
            head = node;
        }
    }

    public void addLast(int data){
        ListNode node = new ListNode(data);
        ListNode cur = head;
        if (head == null){
            head = node;
        }else {
            while (cur.next != null){
                cur = cur.next;
            }
            cur.next = node;
        }
    }

    public boolean contains(int key){
        if (head == null){
            return false;
        }else {
            ListNode cur = head;
            while (cur.next != null){
                if (cur.val == key){
                    return true;
                }
                cur = cur.next;
            }
        }
        return false;
    }

    public void remove(int key){
        if (head == null){
            return;
        }
        if (head.val == key){
            head = head.next;
            return;
        }
        ListNode cur = searchPerv(15);
        if (cur == null){
            return;
        }
        ListNode del = cur.next;
        cur.next = del.next;
    }

    public ListNode searchPerv(int key){
        ListNode cur = head;
        while (cur.next != null){
            if (cur.next.val == key){
                return cur;
            }
            cur = cur.next;
        }
        return null;
    }

    public ListNode removeAllKey(int key){
        if (head == null){
            return null;
        }
        ListNode prev = head;
        ListNode cur = head.next;
        while (cur != null){
            if (cur.val == key){
                prev.next = cur.next;
                cur = cur.next;
            }else {
                prev = cur;
                cur = cur.next;

            }
        }
        if (head.val == key){
            head = head.next;
        }
        return head;

    }

    public void addIndex(int index,int data){
        if (index < 0 || index > size()){
            return;
        }
        if (index == 0){
            addFirst(index);
            return;
        }
        if (index == size()){
            addLast(index);
            return;
        }
        ListNode cur = findIndex(index);
        ListNode node = new ListNode(data);
        node.next = cur.next;
        cur.next = node;

    }

    private ListNode findIndex(int index) {
        ListNode cur = head;
        while (index-1 != 0){
            cur = cur.next;
            index--;
        }
        return cur;
    }


    public ListNode reverseList(ListNode head){
        if (head == null){
            return null;
        }
        ListNode cur = head;
        ListNode curNext = cur.next;
        ListNode prev = null;
        while (cur != null){
            cur.next = prev;
            prev = cur;
            cur = curNext;
        }
        return prev;
    }

    public ListNode middleNode(ListNode head) {
        if (head == null){
            return null;
        }
        ListNode fast = head;
        ListNode slow = head;
        while (fast != null && fast.next != null){
            fast = fast.next.next;
            slow = slow.next;
        }
        return slow;

    }

    public ListNode FindKthToTail(ListNode head,int k) {
        if (k <= 0 || head == null){
            return null;
        }
        ListNode fast = head;
        ListNode slow = head;
        while (k-1 != 0){
            fast = fast.next;
            if (fast == null){
                return null;
            }
            k--;
        }
        while (fast.next != null) {
            fast = fast.next;
            slow = slow.next;
        }

        return slow;


    }

    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        ListNode newHead = new ListNode(0);
        ListNode tmp = newHead;
        while (list1 == null || list2 == null){
            if (list1.val < list2.val){
                tmp.next = list1;
                list1 = list1.next;
                tmp = list1;
            }else {
                tmp.next = list2;
                list2 = list2.next;
                tmp = list2;
            }
        }
        if (list1 == null){
            tmp = list2;
        }
        if (list2 == null){
            tmp = list1;
        }
        return tmp.next;
    }

    public ListNode partition(ListNode pHead, int x) {
        ListNode bs = null ;
        ListNode be = null;
        ListNode as = null;
        ListNode ae = null;
        ListNode cur = head;
        while (cur != null){
            if (cur.val < x){
                if (bs == null){
                    bs = cur;
                    be = cur;
                }else {
                    be.next = cur;
                    be = be.next;
                }
            }else {
                if (as == null){
                    as = cur;
                    ae = cur;
                }else {
                    ae.next = cur;
                    ae = ae.next;
                }
            }
            cur = cur.next;
        }
        if (bs == null){
            return as;
        }
        be.next = as;
        if (as != null){
            ae.next = null;
        }
        return bs;
    }

    public ListNode deleteDuplication(ListNode pHead) {

        ListNode cur = head;
        ListNode newHead = new ListNode(-1);
        ListNode tmp = newHead;
        while (cur != null){
            if (cur.next !=null && cur.val == cur.next.val){
                while (cur.next !=null && cur.val == cur.next.val){
                    cur = cur.next;
                }
            }else {
                tmp.next = cur;
                tmp = tmp.next;
                cur  =cur.next;
            }
        }
        tmp.next = null;
        return newHead.next;
    }




}
